The invention generally relates to computer systems and, more particularly, the invention relates to the rendering of a circle by approximating the circle using the vertices of a polygon.
Some computer graphics systems have hardware dedicated to rendering circles precisely using differentials. Alternatively, computer graphics systems that do not have dedicated hardware for rendering circles typically improve performance by approximating circles using a polygon whose vertices lie along the circumference of the circle. The approximation of a circle by using a polygon with multiple vertices is shown in FIG. 1. A four sided polygon 10 may be used to approximate circle 11. Also shown are an eight sided polygon 12, a twelve sided polygon 14 and a circle 16 approximated by using an infinite number of vertices. The number of vertices required to render a circle is dependent upon the desired accuracy and the radius of the circle itself. The number of vertices is also directly related to the amount of time it takes to render the circle, and therefore, inversely proportional to the performance of the computer graphics system.
In a computer graphics system which approximates a circle using a polygon, typically, sine and cosine functions are used to compute each vertex of the polygon used to approximate the circle. Alternatively, a table of precomputed sine and cosine coordinate values may be used to eliminate the sine and cosine computations on a per-vertex basis. The size of the table of sine and cosine values will determine the number of vertices which are used to approximate a circle. For example, if the computer graphics system has a table with six entries, six vertices will be used to approximate the circle. Since a large number of vertices is required to represent a large circle, then, a large table of sine and cosine values must be created. This same table when used to render a smaller circle, however, will be far more accurate than necessary, and will result in slower performance of the computer graphics system.
In accordance with one aspect of the invention, an apparatus and method for rendering a circle on a display device, the circle having a radius and a circumference, (a) provides a set of vertex points, (b) selects a subset of vertex points from the set of vertex points based on the radius of the circle, (c) scales each vertex point in the subset of vertex points to produce scaled vertex points, and then (d) connects each scaled vertex point in the subset of vertex points to approximate the circle. In a preferred embodiment, the act of scaling comprises multiplying each vertex point by the radius of the circle. The set of vertex points may be stored in a table in a computer memory. In another embodiment, the subset of vertex points is used to determine scaled vertex points for all four quadrants of the circle. In a further preferred embodiment, the members of the subset of vertex points are evenly distributed about the circumference of the circle.
In one embodiment, the aforementioned step (b) may further determine the number of vertex points required to render the circle with an error less than a predetermined error threshold and then select the subset of vertex points such that the number of members in the subset of vertex points is equivalent to the number of vertex points required to render the circle with an error less than the predetermined error threshold. The number of vertex points required to render the circle with an error less than the predetermined error threshold may be determined using the following relationship:   n  =      π          4      ⁢                        cos                      -            1                          ⁡                  (                                    r              -              ϵ                        r                    )                    
where n=number of vertex points; r=radius of the circle; and, xcex5=the predetermined error threshold.
In an alternative embodiment, the aforementioned step (b) may further identify all possible vertex point counts, determine the maximum circle radius which may be rendered using each of the possible vertex point counts such that an error is less than a predetermined error threshold and then select the subset of vertex points by comparing the radius of the circle to each maximum circle radius. The maximum circle radius may be determined using the following relationship:   r  =      ϵ          1      -              cos        ⁡                  (                      π                          4              ⁢              n                                )                    
where r=maximum circle radius; xcex5=the predetermined error threshold; and, n=vertex point count.
In accordance with another aspect of the invention, an apparatus and method for rendering a circle on a display device, the circle having a radius and four quadrants, (a) provides a set of vertex points for one quadrant of the circle, (b) identifies the vertex points for the remaining three quadrants using the set of vertex points, and (c) connects the vertex points of all four quadrants to approximate the circle. In a preferred embodiment, the apparatus and method further comprises multiplying each vertex point in each quadrant by the radius of the circle. The set of vertex points may be stored in a table in a computer memory. In another embodiment, step (b) may further select a subset of vertex points based on the radius of the circle and identify the vertex points for the remaining three quadrants using the members of the subset of vertex points.
Preferred embodiments of the invention are implemented as a computer program product having a computer usable medium with computer readable program code thereon. The computer readable code may be read and utilized by the computer system in accordance with conventional processes.